SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Teknomo–Fernandez algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Teknomo–Fernandez algorithm</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">"TF Algorithm" redirects here. For other uses, see <a href="TF_Algorithm_(disambiguation)" class="mw-redirect mw-disambig" title="TF Algorithm (disambiguation)">TF Algorithm (disambiguation)</a>.</div>

<p>The <b>Teknomo–Fernandez algorithm (TF algorithm)</b>, is an efficient algorithm for generating the background image of a given video sequence.

</p><p>By assuming that the background image is shown in the majority of the video, the algorithm is able to generate a good background image of a video in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(R)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(R)}</annotation>

</semantics>

</math></span><img src="./78dcf1dfcb9e7e9d62c1a9bab49329b4bdff1f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.347ex; height:2.843ex;" alt="{\displaystyle O(R)}" loading="lazy"></span>-time using only a small number of <a href="Binary_operations" class="mw-redirect" title="Binary operations">binary operations</a> and Boolean bit operations, which require a small amount of memory and has built-in operators found in many programming languages such as <a href="C_(programming_language)" title="C (programming language)">C</a>, <a href="C%2B%2B" title="C++">C++</a>, and <a href="Java_(programming_language)" title="Java (programming language)">Java</a>.<sup id="cite_ref-TF_1-0" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-PCTF_2-0" class="reference"><a href="#cite_note-PCTF-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-ITF_3-0" class="reference"><a href="#cite_note-ITF-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>People tracking from videos usually involves some form of <a href="Background_subtraction" class="mw-redirect" title="Background subtraction">background subtraction</a> to segment foreground from background. Once foreground images are extracted, then desired algorithms (such as those for <a href="Video_tracking" title="Video tracking">motion tracking</a>, <a href="Optical_motion_tracking" class="mw-redirect" title="Optical motion tracking">object tracking</a>, and <a href="Facial_recognition_system" title="Facial recognition system">facial recognition</a>) may be executed using these images.<sup id="cite_ref-TF_1-1" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-ITF_3-1" class="reference"><a href="#cite_note-ITF-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>However, <a href="Background_subtraction" class="mw-redirect" title="Background subtraction">background subtraction</a> requires that the background image is already available and unfortunately, this is not always the case. Traditionally, the background image is searched for manually or automatically from the video images when there are no objects. More recently, automatic background generation through <a href="Object_detection" title="Object detection">object detection</a>, medial filtering, medoid filtering, approximated median filtering, linear predictive filter, <a href="Non-parametric_model" class="mw-redirect" title="Non-parametric model">non-parametric model</a>, <a href="Kalman_filter" title="Kalman filter">Kalman filter</a>, and <a href="Adaptive_smoothening" class="mw-redirect" title="Adaptive smoothening">adaptive smoothening</a> have been suggested; however, most of these methods have high computational complexity and are resource-intensive.<sup id="cite_ref-TF_1-2" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-RTTF_4-0" class="reference"><a href="#cite_note-RTTF-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>The Teknomo–Fernandez algorithm is also an automatic background generation algorithm. Its advantage, however, is its computational speed of only <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(R)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(R)}</annotation>

</semantics>

</math></span><img src="./78dcf1dfcb9e7e9d62c1a9bab49329b4bdff1f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.347ex; height:2.843ex;" alt="{\displaystyle O(R)}" loading="lazy"></span>-time, depending on the resolution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> of an image and its accuracy gained within a manageable number of frames. Only at least three frames from a video is needed to produce the background image assuming that for every pixel position, the background occurs in the majority of the videos. Furthermore, it can be performed for both grayscale and colored videos.<sup id="cite_ref-TF_1-3" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Assumptions">Assumptions</h2></div>

<ul><li>The camera is stationary.</li>

<li>The light of the environment changes only slowly relative to the motions of the people in the scene.</li>

<li>The number of people does not occupy the scene for most of the time at the same place.</li></ul><p>

Generally, however, the algorithm will certainly work whenever the following single important assumption holds: </p><blockquote><p>For each pixel position, the majority of the pixel values in the entire video contain the pixel value of the actual background image (at that position).<sup id="cite_ref-TF_1-4" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></p></blockquote><p>As long as each part of the background is shown in the majority of the video, the entire background image needs not to appear in any of its frames. The algorithm is expected to work accurately.<sup id="cite_ref-TF_1-5" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><div class="mw-heading mw-heading2"><h2 id="Background_image_generation">Background image generation</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Equations">Equations</h3></div>

<ol><li>For three frames of image sequence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math></span><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy"></span>, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}}</annotation>

</semantics>

</math></span><img src="./d7af1b928f06e4c7e3e8ebfd60704656719bd766.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{2}}" loading="lazy"></span>, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{3}}</annotation>

</semantics>

</math></span><img src="./766d09a498699be10e276ad49145c921f8cbe335.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{3}}" loading="lazy"></span>, the background image <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> is obtained using <br>     <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}}</annotation>

</semantics>

</math></span><img src="./dfadc793af2f91bf1d077e5998b8717367f86ea6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.272ex; height:2.843ex;" alt="{\displaystyle B=x_{3}(x_{1}\oplus x_{2})+x_{1}x_{2}}" loading="lazy"></span><sup id="cite_ref-TF_1-6" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></li>

<li>The Boolean mode function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> of the table occurs when the number of 1 entries is larger than half of the number of images such that<sup id="cite_ref-TF_1-7" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><br>     <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S={\begin{cases}1,&{\text{if }}\sum _{i=1}^{n}x_{i}\geq \left\lceil {\frac {n}{2}}+1\right\rceil ,{\text{ and }}n\geq 3\\0,&{\text{otherwise}}\end{cases}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S={\begin{cases}1,&{\text{if }}\sum _{i=1}^{n}x_{i}\geq \left\lceil {\frac {n}{2}}+1\right\rceil ,{\text{ and }}n\geq 3\\0,&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math></span><img src="./a7e1681c1e47785f7e215a8faa840888cce57c66.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:44.525ex; height:6.176ex;" alt="{\displaystyle S={\begin{cases}1,&{\text{if }}\sum _{i=1}^{n}x_{i}\geq \left\lceil {\frac {n}{2}}+1\right\rceil ,{\text{ and }}n\geq 3\\0,&{\text{otherwise}}\end{cases}}}" loading="lazy"></span></li>

<li>For three images, the background image <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math></span><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"></span> can be taken as the value</li></ol>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {x}}_{1}x_{2}x_{3}+x_{1}{\bar {x}}_{2}x_{3}+x_{1}x_{2}{\bar {x}}_{3}+x_{1}x_{2}x_{3}}</annotation>

</semantics>

</math></span><img src="./696f4e946a288acdefc2398b998a8a7be2092634.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:37.128ex; height:2.343ex;" alt="{\displaystyle {\bar {x}}_{1}x_{2}x_{3}+x_{1}{\bar {x}}_{2}x_{3}+x_{1}x_{2}{\bar {x}}_{3}+x_{1}x_{2}x_{3}}" loading="lazy"></span> <sup id="cite_ref-TF_1-8" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></dd></dl></dd></dl></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Background_generation_algorithm">Background generation algorithm</h3></div>

<p>At the first level, three frames are selected at random from the image sequence to produce a background image by combining them using the first equation. This yields a better background image at the second level. The procedure is repeated until desired level <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span>.<sup id="cite_ref-TF_1-9" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Theoretical_accuracy">Theoretical accuracy</h2></div>

<p>At level <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell }</annotation>

</semantics>

</math></span><img src="./f066e981e530bacc07efc6a10fa82deee985929e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.97ex; height:2.176ex;" alt="{\displaystyle \ell }" loading="lazy"></span>, the probability <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{\ell }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{\ell }}</annotation>

</semantics>

</math></span><img src="./879db252766602dab3270c175e627b7268b9099b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.177ex; height:2.009ex;" alt="{\displaystyle p_{\ell }}" loading="lazy"></span> that the modal bit predicted is the actual modal bit is represented by the equation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{\ell }=(p_{\ell -1})^{3}+3(p_{\ell -1})^{2}(1-p_{\ell -1})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{\ell }=(p_{\ell -1})^{3}+3(p_{\ell -1})^{2}(1-p_{\ell -1})}</annotation>

</semantics>

</math></span><img src="./45850f015ed1a86715ded066b0c563de4f659ac8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:33.381ex; height:3.176ex;" alt="{\displaystyle p_{\ell }=(p_{\ell -1})^{3}+3(p_{\ell -1})^{2}(1-p_{\ell -1})}" loading="lazy"></span>.

The table below gives the computed probability values across several levels using some specific initial probabilities. It can be observed that even if the modal bit at the considered position is at a low 60% of the frames, the probability of accurate modal bit determination is already more than 99% at 6 levels.<sup id="cite_ref-TF_1-10" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Space_complexity">Space complexity</h2></div>

<p>The space requirement of the Teknomo–Fernandez algorithm is given by the function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(RF+R3^{L})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(RF+R3^{L})}</annotation>

</semantics>

</math></span><img src="./1d9692b58507c66054beb60d2c0d46bde7f33dbd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.206ex; height:3.176ex;" alt="{\displaystyle O(RF+R3^{L})}" loading="lazy"></span>, depending on the resolution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> of the image, the number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F}</annotation>

</semantics>

</math></span><img src="./545fd099af8541605f7ee55f08225526be88ce57.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.741ex; height:2.176ex;" alt="{\displaystyle F}" loading="lazy"></span> of frames in the video, and the desired number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> of levels. However, the fact that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> will probably not exceed 6 reduces the space complexity to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(RF)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(RF)}</annotation>

</semantics>

</math></span><img src="./000fc64a8685aabcde1d3648de8a1f78b965a226.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.087ex; height:2.843ex;" alt="{\displaystyle O(RF)}" loading="lazy"></span>.<sup id="cite_ref-TF_1-11" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Time_complexity">Time complexity</h2></div>

<p>The entire algorithm runs in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(R)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(R)}</annotation>

</semantics>

</math></span><img src="./78dcf1dfcb9e7e9d62c1a9bab49329b4bdff1f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.347ex; height:2.843ex;" alt="{\displaystyle O(R)}" loading="lazy"></span>-time, only depending on the resolution of the image. Computing the modal bit for each bit can be done in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span>-time while the computation of the resulting image from the three given images can be done in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(R)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(R)}</annotation>

</semantics>

</math></span><img src="./78dcf1dfcb9e7e9d62c1a9bab49329b4bdff1f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.347ex; height:2.843ex;" alt="{\displaystyle O(R)}" loading="lazy"></span>-time. The number of the images to be processed in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L}</annotation>

</semantics>

</math></span><img src="./103168b86f781fe6e9a4a87b8ea1cebe0ad4ede8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.583ex; height:2.176ex;" alt="{\displaystyle L}" loading="lazy"></span> levels is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(3^{L})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(3^{L})}</annotation>

</semantics>

</math></span><img src="./cc9416b3e6f6c2008c5b61b9b88b491d5ee78001.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.097ex; height:3.176ex;" alt="{\displaystyle O(3^{L})}" loading="lazy"></span>. However, since <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\leq 6}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\leq 6}</annotation>

</semantics>

</math></span><img src="./3a6e0fbcda842fd53f07c797d82030ccb40cbd75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.844ex; height:2.343ex;" alt="{\displaystyle L\leq 6}" loading="lazy"></span>, then this is actually <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span>, thus the algorithm runs in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(R)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(R)}</annotation>

</semantics>

</math></span><img src="./78dcf1dfcb9e7e9d62c1a9bab49329b4bdff1f9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.347ex; height:2.843ex;" alt="{\displaystyle O(R)}" loading="lazy"></span>.<sup id="cite_ref-TF_1-12" class="reference"><a href="#cite_note-TF-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Variants">Variants</h2></div>

<p>A variant of the Teknomo–Fernandez algorithm that incorporates the <a href="Monte-Carlo_method" class="mw-redirect" title="Monte-Carlo method">Monte-Carlo method</a> named CRF has been developed. Two different configurations of CRF were implemented: CRF9,2 and CRF81,1. Experiments on some colored video sequences showed that the CRF configurations outperform the TF algorithm in terms of accuracy. However, the TF algorithm remains more efficient in terms of processing time.<sup id="cite_ref-CRF_5-0" class="reference"><a href="#cite_note-CRF-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<ul><li><a href="Object_detection" title="Object detection">Object detection</a></li>

<li><a href="Face_detection" title="Face detection">Face detection</a></li>

<li><a href="Face_recognition" class="mw-redirect" title="Face recognition">Face recognition</a></li>

<li><a href="Pedestrian_detection" title="Pedestrian detection">Pedestrian detection</a></li>

<li><a href="Video_surveillance" class="mw-redirect" title="Video surveillance">Video surveillance</a></li>

<li><a href="Motion_capture" title="Motion capture">Motion capture</a></li>

<li><a href="Human-computer_interaction" class="mw-redirect" title="Human-computer interaction">Human-computer interaction</a></li>

<li>Content-based video coding</li>

<li>Traffic monitoring</li>

<li>Real-time <a href="Gesture_recognition" title="Gesture recognition">gesture recognition</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFTeknomoFernandez2015" class="citation arxiv cs1">Teknomo, Kardi; Fernandez, Proceso (2015). "Background Image Generation Using Boolean Operations". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1510.00889">1510.00889</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.CV">cs.CV</a>].</cite></span>

</li>

<li id="cite_note-PCTF-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-PCTF_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFAbuFernandez2014" class="citation book cs1">Abu, Patricia Angela; Fernandez, Proceso (2014). "Performance Comparison of the Teknomo-Fernandez Algorithm on the RGB and HSV Colour Spaces". <i>2014 International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM)</i>. pp. <span class="nowrap">1–</span>6. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FHNICEM.2014.7016262">10.1109/HNICEM.2014.7016262</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4799-4020-2</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15493318">15493318</a>.</cite></span>

</li>

<li id="cite_note-ITF-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-ITF_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-ITF_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFAbu2015" class="citation thesis cs1">Abu, Patricia Angela (March 2015). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/273445070"><i>Improving the Teknomo–Fernandez Background Image Modeling Algorithm for Foreground Segmentation</i></a> (Ph.D). Ateneo de Manila University.</cite></span>

</li>

<li id="cite_note-RTTF-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-RTTF_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFAbuFernandez2016" class="citation conference cs1">Abu, Patricia Angela; Fernandez, Proceso (March 2016). <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/298791390"><i>Modifying the Teknomo–Fernandez Algorithm for Accurate Real-Time Background Subtraction</i></a>. Philippine Computing Science Congress.</cite></span>

</li>

<li id="cite_note-CRF-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-CRF_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFAbuChuFernandez" class="citation journal cs1">Abu, Patricia Angela; Chu, Varian Sherwin; Fernandez, Proceso. <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/273391116">"A Monte-Carlo-based Algorithm for Background Generation"</a>.</cite> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{cite journal}}</code>: </span><span class="cs1-visible-error citation-comment">Cite journal requires <code class="cs1-code">|journal=</code> (help)</span></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFChu2013" class="citation thesis cs1">Chu, Varian Sherwin B. (2013). <i>Background image reconstruction using random frame sampling and logical bit operations</i> (Thesis). Ateneo de Manila University.</cite></li>

<li><cite id="CITEREFAbu2015" class="citation thesis cs1">Abu, Patricia Angela R. (2015). <i>Improving the Teknomo-Fernandez Background Image Modeling Algorithm for Foreground Segmentation</i> (Thesis). Ateneo de Manila University.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1510.00889">Background Image Generation Using Boolean Operations</a> – describes the TF algorithm, its assumptions, processes, accuracy, time and space complexity, and sample results.</li>

<li><a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/273391116_A_Monte-Carlo-based_Algorithm_for_Background_Generation">A Monte-Carlo-based Algorithm for Background Generation</a> – a variant of the Teknomo–Fernandez algorithm that incorporates the <a href="Monte-Carlo_method" class="mw-redirect" title="Monte-Carlo method">Monte-Carlo method</a> was developed in this study.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-10-14" href="https://en.wikipedia.org/wiki/?title=Teknomo%E2%80%93Fernandez_algorithm&oldid=1251189377">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>